#!/bin/env python
# -*- coding:utf-8
"""
@author:xingz
@file:maze.py
@time:2022/02/16
"""
from enum import Enum
from typing import *
import random
from zx_search.generic_search import *
from zx_search.generic_search import dfs
from math import sqrt


class Cell(str, Enum):
    EMPTY = " "
    BLOCKED = "X"
    START = "S"
    GOAL = "G"
    PATH = "*"


class MazeLocation(NamedTuple):
    row: int
    column: int


class Maze:
    def __init__(self, rows: int = 10, columns: int = 10, sparseness: float = 0.2, start: MazeLocation = MazeLocation(0, 0), goal: MazeLocation = MazeLocation(9, 9)):
        """
        :param rows:迷宫行数
        :param columns: 迷宫列数
        :param sparseness: 迷宫稀疏度
        :param start: 起始位置
        :param goal: 目标位置
        """
        self._rows = rows
        self._columns = columns
        self.start: MazeLocation = start
        self.goal: MazeLocation = goal
        self._grid: List[List[Cell]] = [[Cell.EMPTY for c in range(columns)] for r in range(rows)]
        self._randomly_fill(rows, columns, sparseness)
        self._grid[start.row][start.column] = Cell.START
        self._grid[goal.row][goal.column] = Cell.GOAL
        pass

    @property
    def grid(self):
        return self._grid

    @property
    def rows(self):
        return self._rows

    @property
    def columns(self):
        return self._columns

    def _randomly_fill(self, rows: int, columns: int, sparseness: float):
        for row in range(rows):
            for col in range(columns):
                if random.uniform(0, 1.0) < sparseness:
                    self._grid[row][col] = Cell.BLOCKED

    # return a nicely formatted version of the maze for printing.
    def __str__(self):
        out = ""
        for row in range(len(self._grid)):
            out += "\t".join([c.value for c in self._grid[row]]) + "\n"
        return out

    def goal_test(self, ml: MazeLocation) -> bool:
        if ml.row == self.goal.row and ml.column == self.goal.column:
            return True
        else:
            return False

    def successor(self, ml: MazeLocation) -> List[MazeLocation]:
        locations: List[MazeLocation] = []
        if ml.row + 1 < self._rows and self._grid[ml.row + 1][ml.column] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row + 1, ml.column))
        if ml.row - 1 > 0 and self._grid[ml.row - 1][ml.column] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row - 1, ml.column))
        if ml.column + 1 < self._columns and self._grid[ml.row][ml.column + 1] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row, ml.column + 1))
        if ml.column - 1 > 0 and self._grid[ml.row][ml.column - 1] != Cell.BLOCKED:
            locations.append(MazeLocation(ml.row, ml.column - 1))
        return locations

    def mark(self, path: List[MazeLocation]):
        for location in path:
            self._grid[location.row][location.column] = Cell.PATH
        self._grid[self.start.row][self.start.column] = Cell.START
        self._grid[self.goal.row][self.goal.column] = Cell.GOAL

    def clear(self, path: List[MazeLocation]):
        for location in path:
            self._grid[location.row][location.column] = Cell.EMPTY
        self._grid[self.start.row][self.start.column] = Cell.START
        self._grid[self.goal.row][self.goal.column] = Cell.GOAL


def euclidean_distance(goal: MazeLocation) -> Callable[[MazeLocation], float]:
    def distance(ml: MazeLocation) -> float:
        xdist = ml.column - goal.column
        ydist = ml.row - goal.row
        return sqrt((xdist * xdist) + (ydist * ydist))

    return distance


def manhattan_distance(goal: MazeLocation) -> Callable[[MazeLocation], float]:
    def distance(ml: MazeLocation):
        xdis = ml.column - goal.column
        ydis = ml.row - goal.row
        return xdis + ydis

    return distance


if __name__ == '__main__':
    # Test DFS
    m = Maze()
    print(m)
    solution1: Optional[Node[MazeLocation]] = dfs(m.start, m.goal_test, m.successor)
    solution2: Optional[Node[MazeLocation]] = bfs(m.start, m.goal_test, m.successor)
    if solution1 is None:
        print("No solution found using depth-first search!")
    if solution2 is None:
        print("No solution found using breadth-first search!")
    else:
        path1 = node_to_path(solution1)
        path2 = node_to_path(solution2)
        m.mark(path1)
        print(m)
        m.clear(path1)
        m.mark(path2)
        print(m)
        m.clear(path2)
